package leetcode.code0331;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：1 ms, 在所有 Java 提交中击败了98.89%的用户
//
//内存消耗：40.1 MB, 在所有 Java 提交中击败了5.15%的用户
//
//通过测试用例：151 / 151
public class Solution implements IDebug {

	public boolean isValidSerialization(String preorder) {
		char[] pd = preorder.toCharArray();
		int len = pd.length;
		char[] stack = new char[len];
		int pstack = 0;
		for (int i = 0; i <= len; i++) {
			if (i == len || pd[i] == ',') {
				char c = pd[i - 1];
				// 9,3,4,#,#,1,#,#,2,#,6,#,#
				// 9,#,2,#,6,#,#
				if (c == '#' && pstack != 0 && stack[pstack - 1] == '#') {
					stack[pstack++] = c;
					while (pstack - 1 >= 0 && stack[pstack - 1] == '#' && pstack - 2 >= 0 && stack[pstack - 2] == '#') {
						pstack -= 2;
						if (pstack > 0) {
							stack[pstack - 1] = '#';
						} else {
							return false;
						}
					}
				} else {
					stack[pstack++] = c;
				}
			}
		}
		return pstack == 1 && stack[0] == '#';
	}

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(false, this.isValidSerialization("1,#"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(false, this.isValidSerialization("9,#,#,1"));

	}

	@Override
	public void debug4() {
		HelpDebug.compare(true, this.isValidSerialization("9,3,4,#,#,1,#,#,2,1,#,#,6,#,#"));

	}

	public void debug5() {
		HelpDebug.compare(false, this.isValidSerialization("1"));

	}

	public void debug6() {
		HelpDebug.compare(false, this.isValidSerialization("1,#,#,#,#"));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();

	}

}
